package com.dmall.play.interview.chapter09;

import java.util.ArrayList;
import java.util.List;

/**
 * 记忆化搜索
 */
public class Leetcode120V2 {

    private Integer[][] dp = null;

    public int minimumTotal(List<List<Integer>> triangle) {
        dp = new Integer[triangle.size()][triangle.size()];
        dp[0][0] = triangle.get(0).get(0);
        List<Integer> lastRow = triangle.get(triangle.size() - 1);
        int lastRowSize = lastRow.size();
        for (int i = 0; i < lastRowSize; i++) {
            backTrack(triangle, triangle.size() - 1, i);
        }
        Integer[] minPathArr = dp[triangle.size() - 1];
        int minPathTotal = Integer.MAX_VALUE;
        for (Integer integer : minPathArr) {
            minPathTotal = Math.min(minPathTotal, integer);
        }
        return minPathTotal;
    }

    private int backTrack(List<List<Integer>> triangle, int row, int col) {
        if (dp[row][col] != null) {
            return dp[row][col];
        }
        if (col == 0) {
            return dp[row][col] = backTrack(triangle, row - 1, col) + triangle.get(row).get(col);
        }
        if (col == row) {
            return dp[row][col] = backTrack(triangle, row - 1, col - 1) + triangle.get(row).get(col);
        }
        int left = backTrack(triangle, row - 1, col);
        int right = backTrack(triangle, row - 1, col - 1);
        return dp[row][col] = Math.min(left, right) + triangle.get(row).get(col);
    }

    public static void main(String[] args) {
        List<List<Integer>> triangle = new ArrayList<>();
        List<Integer> item1 = new ArrayList<>();
        item1.add(2);
        List<Integer> item2 = new ArrayList<>();
        item2.add(3);
        item2.add(4);
        List<Integer> item3 = new ArrayList<>();
        item3.add(6);
        item3.add(5);
        item3.add(7);
        List<Integer> item4 = new ArrayList<>();
        item4.add(4);
        item4.add(1);
        item4.add(8);
        item4.add(3);
        triangle.add(item1);
        triangle.add(item2);
        triangle.add(item3);
        triangle.add(item4);

        Leetcode120V2 leetcode120 = new Leetcode120V2();
        int minimumTotal = leetcode120.minimumTotal(triangle);
        System.out.println(minimumTotal);
    }
}
